package com.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class L0015 {
    public static void main(String[] args) {
        int[] arr = {-1, 0, 1, 2, -1, -4};
        System.out.println(threeSum(arr));
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            int num = 0 - nums[i];
            int per = i + 1;
            int last = nums.length - 1;
            while (per < last) {
                if (nums[per] + nums[last] == num){
                        List<Integer> list = Arrays.asList(nums[i], nums[per], nums[last]);
                        res.add(list);
                        while (nums[per] == nums[per + 1] && per < last)
                            per++;
                        while (nums[last] == nums[last - 1] && per < last)
                            last--;
                    }
                    if (nums[per] + nums[last] > num) {
                        last--;
                    } else {
                        per++;
                    }
                }
            }
        return res;
    }
}